Det finns nog ingen van användare av Internet i dag

som inte märkt av begränsningarna i överföringshastigheten.

Problemet kommer nog inte att bli mindre heller. I alla

fall inte om idéer som TV över Internet blir verklighet.

För att Internet och andra nätverk inte ska "slamma

igen" helt måste man komprimera stora filer som videofiler.

MPEG (Moving Pictures Expert Group) är en grupp som

sammanträder fyra gånger om året, en vecka åt gången och

fastställer videokomprimerings standarder. MPEG är ett

smeknamn för ISO/IEC JTC1 SC29 WG11. Hittills har man

kommit fram till standarderna MPEG 1, 2 och 4. MPEG 3

har också funnits men den integrerades i MPEG 2. Dessa är

optimerade för olika överföringshastigheter och kvalitet.

Själva komprimeringen är den samma hos alla typer av MPEG.

Det är en så kallad "lossy" komprimering. "Lossy" är engelska

och står för att man tappar något i innehållet när man

komprimerar. Man skalar helt enkelt bort information i bilden

som det mänskliga ögat ändå inte märker. Att man tappar

information är ett måste då motsvarigheten, "lossless"

komprimering bara kan komprimera upp till 2:1. Exakt vad det

mänskliga ögat kan och inte kan se är det självklart ingen som

vet. Något man däremot är säker på är att ögat är känsligare för

kontrastskillnader än nyansskillnader. Ögat är också mer

känsligt för lågfrekventa- än högfrekventa förändringar.

MPEG 1

MPEG 1 består av 5 varianter som alla ingår i ISO-standarden

ISO/IEC 11172. Den är skapad för komprimering av så kallade

progressiva videosekvenser på t ex CD-ROM. Progressiva

sekvenser har man när varje bild visar en komplett

ögonblicksbild av motivet. Motsatsen kallas sammanvävd

sekvens och där är informationen lagrad i två fält. Ett fält med

alla jämna rader och ett med alla udda. PAL, SECAM

och NTSC som är standarder för olika TV-signaler använder

alla sammanvävd sekvens. Det ger problem när man ska göra

om TV-signalen till en MPEG 1 sekvens. För TV-distribution

gav MPEG 1 också för dålig bildkvalitet p g a komprimerings

algoritmen skalade bort för mycket av datan.

MPEG 2

Därför utvecklades MPEG 2 som ger bättre bildkvalitet och

klarar av sammanflätade sekvenser. MPEG 2 kräver därför

också högre hastighet och större filer. Den används till bl a

DVD-video och Digital-TV.

MPEG 4

Det senaste tillskottet i MPEG-familjen heter MPEG 4. Den är

avsedd till videotelefoner och dyl. där överföringshastigheten

och kraven på bildkvaliteten är lägre. Här har man reducerat

antalet bilder/sekund till ca 10 st jämfört med MPEG 1 och

MPEG 2 där man vanligen har 24 bilder/sekund. TV i Sverige

(PAL) använder 50 fält/sekund. Eftersom ett fält bara

innehåller halva bilden betyder det att man har 25 helt nya

bilder per sekund.

Färgrymden

I MPEG använder man sig av färgrymden YCrCb, där Y

står för luminansen, eller ljusstyrkan, i en punkt och Cr och

Cb står för krominansen eller färgförhållandet. I

datorsammanhang i övrigt använder man sig oftast av RGB

där parametrarna står för mängden rött, grönt och blått i en

punkt. En fördel med YCrCb är att ljusstyrkan och

färgförhållandet är separerade från varandra. Eftersom att

ögat är mindre känsligt för skillnader i färgförhållandet

"subsamplar" man krominansparametrarna. Det betyder

att man tar bort t ex varannan krominansparameter och

på så vis får mindre data kvar.

Övergång från RGB till YCrCb grafiskt ill.

Det vanligaste förekommande krominansformatet kallas

4:2:0 och där har man tagit bort ¾ av färgförhållandena

utan att ögat uppfattar det som en nämnvärd försämring.

På det här viset har man skalat bort hälften av

informationsmängden. Det ingår dock inte i själva

MPEG-komprimeringen då MPEG utgår från videosekvenser

som representeras i denna färgrymd.

Komprimeringen

Bildtyper

I MPEG finns det tre olika typer av bilder. I-, P- och B-bilder.

I-bild ("intra coded picture", internt kodad bild): Denna typ av

bild kodas helt fristående utan referenser till andra bilder i

sekvensen. Bilden är dock uppdelad i block som kan referera

till varandra. Vid omstart av uppspelningen av sekvensen måste

uppspelningen börja på en sådan här bild. För att man ska kunna

spola i sekvensen bör det vara en I-bild ungefär var 0.4 sekund.

P-bild ("predictive coded picture", förutsagd bild): Denna typ

innehåller referenser till föregående bild. Det som inte går att

referera till föregående bild kodas som i I-bilderna.

B-bild ("biderctionally predictive coded picture",

tvåvägs-förutsagd bild): Denna bildtyp innehåller referenser till

föregående och nästkommande bild. Det gör den lite krångligare

då nästkommande bild måste dekomprimeras före B-bilden.

Avkodningen blir inte längre linjär utan man måste hoppa fram

och tillbaka. B-bilder används vid panoreringar där bilden kan

beskrivas som ett medelvärde av de två omgivande bilderna.

Hur ska man då koda en bestämd bild?

Några saker som algoritmen som bestämmer bildval skall ta

hänsyn till är:

Har det precis varit scenbyte? Då kan det vara svårt att hitta

likheter så välj att I-koda bilden.

När var det senast en I-bild? Var det ungefär 0.4 sekunder eller

10-12 bilder sedan så är det dags för en I-bild.

Är alla rörelser linjära? I sådana fall lämpar sig en B-bild bra.

Har det inte hänt så mycket sedan föregående bild? Då är nog en

P-bild en bra ide.

Det blir svårt att bestämma vilken bildtyp man ska använda när

t ex rörelserna är nästan linjära eller när bilden är ganska lik den

föregående. Därför är det enklast att bara bestämma sig för ett

visst mönster att följa vid kodningen. När det sedan kommer

ett scenbyte är det bara att avbryta mönstret och börja om med

en I-bild. Ett vanligt sådant mönster är

IBBPBBPBB IBBPBBPBB. Om man vill göra det ännu enklare

för sig kan man göra som på företaget Xing Technologies.

Där använder de sig bara av I-bilder. Sekvenserna blir över

dubbelt så stora då men det är betydligt enklare att både

komprimera och dekomprimera.

Rörelsekompensation

Rörelsekompensation görs bara för P- och B-bilder. För varje

block (vanligen 8*8 punkter) i en P-bild görs en sökning i

föregående bild efter ett tillräckligt likt block. Informationen i

blocket ersätts då med en vektor som beskriver hur mycket

blocket i referensbilden är förskjuten. En matris med feltermer

som beskriver vad som inte är sig likt behövs eventuellt.

Flödesschema över rörelsekompensation och kodning av P-bild.

För att snabba upp sökningen bör man ha följande punkter i

betänkande:

Det behövs ingen rörelsekompensation om bilden inte har

förändras överhuvudtaget sedan föregående bild.

Om alla matchningar hittills har gjorts med samma förskjutning

så kan man börja leta åt det hållet.

Vid panoreringar är det onödigt att leta efter de block som

tillkommit vid kanten på bilden.

Vilket är bäst: Bra matchningar eller sämre matchningar med

fler likadana rörelsevektorer? (Många likadana rörelsevektorer

går bättre att komprimera med Huffmankodningen senare i

processen)

Om det är en B-bild man kodar så behöver inte blocken i de

omgivande bilderna vara lika B-bildens block. Huvudsaken

är att deras medelvärden är likt blocket i B-bilden.

De uppkomna feltermer och block som inte gick att matcha går

nu igenom Den Diskreta Cosinustransformen, Kvantisering och

Sicksack-scanning. Det gör inte rörelsevektorerna.

Den Diskreta Cosinustransformen

Det är en transform som gör om alla block med parametrar till

lika stora frekvensblock. I översta vänstra hörnet av blocken

placeras de lågfrekventa parametrarna och frekvensen ökar

successivt mot det nedre högra hörnet i blocken.

Den Diskreta Cosinustransformen.

Kvantisering

Värderna i frekvensblocken divideras ner enligt en

kvantiseringsmatris och avrundas. På så vis får man många lika

värden som är tacksamma att Huffmankomprimera.

Ex:	binärt talsyst.       "vanliga" talsyst.

	101101           =  45 (6 bitar)

	1011               =  11 (kapa till 4 bitar)

	101                 =  5 (kapa till 3 bitar)

I Kvantiseringen tillkommer den största delen av felen in i

MPEG-sekvensen. Desto mer man kapar eller dividerar desto

större blir felet.

Sicksack-scanning

Här plockas blocken sönder till en vektor. En så kallad bitström.

Det gör man i ett speciellt sicksack-mönster. Detta för att

gruppera de lågfrekventa koefficienterna i början av vektorn.

Med ett 8*8 punkters block ser det ut så här:

Sicksack-scanning av ett 8*8 punkters block till en 64*1 vektor

Huffmankodningen

Både rörelsevektorerna och vektorerna från Sicksack-scanningen

entropitetskodas här. Det är egentligen ingen äkta

Huffmankodning. På engelska heter metoden "Variable Length

Coding" (VLC) och är en lätt modifierad variant av

Huffmankodning. Metoden går ut på att man bygger upp ett så

kallat Huffmanträd eller binärträd. Man börjar med att

rangordna parametrarna efter förekomst. Med sekvensen

0, 0, 0, 11, 0, 0, 23, 23, 23, 0, 0, 14, 11, 0, 0, 18, 18, 14, 18, 18

så blir rangordningen: 0 (9 st), 18 (4 st), 23 (3 st), 11 (2 st) och

14 (2 st). Därefter låter man de två ovanligaste parametrarna

(11 och 14) bli de två yttersta lövnoderna i trädet:

De två lövnoderna skall nu ses som ett objekt, A, med förekomsten 2 st + 2st = 4st

Nu upprepar man proceduren och tar ut de två ovanligaste

parametrarna (23 och trädet A). Så fortsätter man så här tills

man har ett helt träd med den vanligaste parametern i toppen.

Huffman-träd

Varje vänster gren i trädet låter man motsvaras av biten "0" och

varje högergren av biten "1". Siffrorna kommer då att kunna

ersättas av den bitsekvens som beskriver vägen till dem genom

trädet: 0="0", 18="10", 23="110", 14="1110" och 11="1111".

Hela sekvensen blir då: "0001111001101101100011101111001"

vilket är 42 bitar. Där till kommer naturligtvis datan som

innehåller själva Huffmanträdet men förtjänsten är ändock

stor. Datorn lagrar normalt alla värden binärt enligt ASCII-tabellen

och då behövs det 8 bitar per tecken. Okodad skulle alltså

sekvensen ta 8*20 = 160 bitar.

Dekomprimering

Nu är MPEG-sekvensen färdig kodad. Dekomprimeringen går till på

exakt samma sätt bortsett från att man gör allt baklänges.

Komprimeringsgraden

Den optimala komprimeringen för MPEG 2 ger en bitström med

ungefär 1,2 bitar/bildpunkt för I-bilder och 0,35 bitar/bildpunkt

för P- och B-bilder. Det innebär en komprimeringsgrad på 6:1

respektive 20:1. Vid lagom blandning av bildtyperna blir det en

total komprimering på drygt 18:1. Det går naturligtvis att

komprimera mycket mer än så men då börjar det dyka upp

synliga fel.

Referenser:

Che-Cher, Chen. "Survey and Implementation of A Distributed MPEG Video Player."
[http://hpc.ee.ntu.edu.tw/~murphy/reports/MMnet/final/MMFinalReport.html]. Aug 1998.

Okänd. "KOMPRIMERING och FILFORMAT."
[http://www.tfe.umu.se/courses/systemteknik/Multimed1/video/komp.html]. Mar 1998.

Okänd. "Komprimering på Internet."

[http://www.island.liu.se/~i94chrob/kom_pa_internet_slutkomm.html].
Apr 1998.

Okänd. "MOVING PICTURE EXPERT GROUP (MPEG)."

[http://www.hogent.be/chroma/MPEGs.html].

Jun 1997.

Söderström, Kjell. "GRAFISKA FILFORMAT."

[http://www.nti.se/~kjell/btt/filformat.html]. Maj 1997.

Terje, Dalen. "Introduksjon til MPEG-1."

[http://multimedia.itek.norut.no/LAVA/MPEG/MPEG1-intro.html].

Okt 1995.

Vinjar, Anders. "KVANTISERING."

[http://www.notam.uio.no/open/settekasse/DSP/DSP/node4.html]. Nov 1996.